package com.simple;

/**
 * 14. 最长公共前缀
 * 编写一个函数来查找字符串数组中的最长公共前缀。
 * 如果不存在公共前缀，返回空字符串 ""。
 */
public class Question14 {

    public static void main(String[] args) {
        String[] strings = new String[]{"reflower", "flow", "flight"};
        System.out.println(longestCommonPrefix(strings));
    }

    /**
     * 思路
     * 1. 找到数组中长度最小的字符串
     * 2. 循环最小字符串中的最小长度的子串
     * 2.1 去每个字符串中判断是否包含当前字符串
     * 如果全部字符串前缀是否相同，则最小长度+1，继续取子串
     * 直到全部字符遍历完成，或有字符串不包含子串
     */
    private static String longestCommonPrefix(String[] strs) {
        if (strs.length < 1) {
            return "";
        }

        String minStr = strs[0], result = "";
        // 找到当前最小字符串
        for (int i = 1; i < strs.length; i++) {
            if (strs[i].length() < minStr.length()) {
                minStr = strs[i];
            }
        }

        // 循环直到最大公共前缀
        for (int i = 1; i <= minStr.length(); i++) {
            String s = minStr.substring(0, i);
            for (String s1 : strs) {
                if (s1.length() < s.length() || !s1.substring(0, i).equals(s)) {
                    return result;
                }
            }
            result = s;
        }

        return result;
    }
}
